package tree;

import java.util.LinkedList;
import java.util.Queue;

//二叉树的每一个结点
class Node {
    public String val;
    //每个结点的子树用 left 和 rigjt 来指向
    public Node left;
    public Node right;
    //构造方法
    public Node(String val){
        this.val = val;
        this.left = null;
        this.right = null;
    }
}
//需要一个树的根结点来拿到整个树
class Tree {
    public Node root;
}

public class Test1 {
    //手动创建一个树
    public static Node creatTree(){
        Node a = new Node("A");
        Node b = new Node("B");
        Node c = new Node("C");
        Node d = new Node("D");
        Node e = new Node("E");
        Node f = new Node("F");
        Node g = new Node("G");
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.right = f;
        e.left = g;
        return a;
    }

    //先序遍历
    public static void preOrder(Node root){
        if (root == null){
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //中序遍历
    public static void inOrder(Node root){
        if (root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    //后序遍历
    public static void postOrder(Node root){
        if (root == null){
            return;
        }
        inOrder(root.left);
        inOrder(root.right);
        System.out.print(root.val + " ");
    }
    //层序遍历
    public static void levelOrder(Node root){
        if(root == null){
            return;
        }
        //先准备一个队列
        Queue<Node> queue = new LinkedList<>();
        //先把根结点入队列
        queue.offer(root);

        //出队列 ，然后把出队列的子树入队列
        //进行循环
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null){
                queue.offer(cur.left);
            }
            if (cur.right != null){
                queue.offer(cur.right);
            }
        }
    }
    public static void main(String[] args) {
        //tree 来表示一颗树
        //Tree tree = new Tree();
        Node root = creatTree();
        preOrder(root);
        System.out.println();
        inOrder(root);
        //System.out.println();
        //preOrder(root);
        //System.out.println();
        //levelOrder(root);
    }
}
